package 图;

/**
 * 130. 被围绕的区域
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域：
 *
 * 连接：一个单元格与水平或垂直方向上相邻的单元格连接。
 * 区域：连接所有 'O' 的单元格来形成一个区域。
 * 围绕：如果您可以用 'X' 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 'X' 单元格围绕。
 * 通过 原地 将输入矩阵中的所有 'O' 替换为 'X' 来 捕获被围绕的区域。你不需要返回任何值。
 *
 * 解题思路：
 *  要解决“被围绕的区域”问题，关键思路是逆向处理：
 *  先标记所有无法被围绕的 'O'（即边界或与边界相连的 'O'），再将剩余的 'O' 转为 'X'。
 *  具体步骤如下：
 *      1、处理边界：
 *          遍历网格的四个边界（第一行、最后一行、第一列、最后一列）；
 *          如果发现边界上的 'O'，通过 DFS 或 BFS 标记所有与之相连的 'O'（临时改为特殊符号如 #）。
 *      2、处理内部区域：
 *          遍历整个网格，将未被标记的 'O'（即被围绕的）转为 'X'，同时将标记过的 # 恢复为 'O'。
 *
 */
public class L_130 {

    public void solve(char[][] board) {
        if(board == null || board.length == 0){
            return;
        }
        // 先把行与列定义出来，减少重复代码以及更直观
        int rows = board.length;
        int cols = board[0].length;
        // 1、先处理左右边界
        for (int i = 0; i < rows; i++) {
            // 左边界
            if (board[i][0] == 'O'){
                dfs(board, i, 0);
            }
            // 右边界
            if(board[i][cols-1] == 'O'){
                dfs(board, i, cols-1);
            }
        }
        // 2、再处理上下边界
        for (int j = 0; j < cols; j++) {
            // 上边界
            if(board[0][j] == 'O'){
                dfs(board, 0, j);
            }
            // 下边界
            if(board[rows-1][j] == 'O'){
                dfs(board, rows-1, j);
            }
        }
        // 最后遍历数组，恢复特殊标记以及将剩余的O标记为X
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }else if(board[i][j] == '#'){
                    board[i][j] = 'O';
                }
            }
        }
    }

    /**
     * 递归标记边界上的O区域
     * @param board
     * @param i
     * @param j
     */
    private void dfs(char[][] board, int i, int j){
        // 非O的返回
        if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] != 'O'){
            return;
        }
        board[i][j] = '#'; // 标记为特殊符号
        // 递归处理上下左右四个方向
        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }
}
